COMMENT ⊗   VALID 00005 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.require "memo.pub[let,jmc]" source
C00043 00003	.SKIP TO COLUMN 1
C00052 00004	.skip 1
C00059 00005	Comments by Carl Hewitt on an earlier version and their fate in this version.
C00066 ENDMK
C⊗;
.require "memo.pub[let,jmc]" source;
.turn off "{"
%2This draft gives insufficient mention to many
people who helped implement LISP and who contributed ideas.
Suggestions for improvements in that directions are particularly
welcome.  Facts about the history of FUNARG and uplevel addressing
generally are especially needed%1.

.cb HISTORY OF LISP

1. Introduction.

	This paper concentrates on the development of the basic
ideas and distinguishes two periods - Summer 1956 through Summer
1958 when most of the key ideas were developed
(some of which were implemented in the FORTRAN based FLPL),
and Fall 1958 through
1962 when the programming language was implemented and applied to
problems of artificial intelligence.  The scope of this conference
does not go beyond that period, and anyway after 1962,
the development of LISP became multi-stranded with different ideas
being pursued in different places.

	As a programming language, LISP is characterized by the following
ideas:  computing with symbolic expressions rather than numbers,
representation of symbolic expressions and other information by list
structure in the memory of a computer,
representation of information in external media by atoms and lists and
secondarily by S-expressions,
a small set of selector and constructor
operations expressed as functions,
composition of functions as a tool for
forming more complex functions,
the use of conditional expressions for
getting branching into function definitions,
the recursive use of
conditional expressions as a sufficient tool for building computable
functions,
the use of λ-expressions for naming functions,
the representation of LISP programs as LISP data,
the conditional expression interpretation of Boolean connectives,
the LISP function %2eval%1 that
serves both as a formal definition of the language and as an interpreter,
and
garbage collection as a means of handling the erasure problem.
LISP statements are also used as a command language when LISP is used
in a time-sharing environment.

	Some of these ideas were taken from other languages but most were
new.  Towards the end of the initial period, it became clear that this
combination of ideas made an elegant mathematical system as well as a
practical programming language.  Then mathematical neatness became a goal
and led to pruning some features from the core of the language.  This was
partly motivated by esthetic reasons and partly by the belief that it
would be easier to devise techniques for proving programs correct if the
semantics were compact and without exceptions.


2. LISP prehistory - Summer 1956 through Summer 1958.

	The desire to design a list processing language for artificial
intelligence work on the IBM 704 computer arose in the summer of 1956 at
the time of the Dartmouth Summer Research Project on Artificial
Intelligence,
which was the first organized study of AI.
The suitability of list processing for AI research was
first pointed out by Newell, Shaw and Simon when they described their
Logic Theorist program and its implementation in IPL 2 on the JOHNNIAC
computer at RAND Corporation.  There was little temptation to copy IPL,
because its form was based on a JOHNNIAC loader that happened to be
available to them, and because the FORTRAN idea of writing programs
algebraically was attractive.  It was immediately apparent
that arbitrary subexpressions of symbolic expressions could be obtained by
composing the functions that extract immediate subexpressions, and this
seemed reason enough to go to an algebraic language.

	There were two motivations for developing a language for the IBM
704.  First, IBM had generously undertaken to establish a New England
Computation Center at M.I.T., and Dartmouth would be able to use it.
Second, IBM was undertaking to develop a program for proving theorems in
plane geometry (based on an idea of Marvin Minsky's), and I was to serve
as a consultant to that project.  At the time, IBM looked like a good bet
to pursue artificial intelligence research vigorously, and further
projects were expected.  Moreover, my own research in artificial
intelligence was proceeding along the lines that led to the Advice Taker
proposal in 1958.  This project involved representing information about
the world by sentences in a suitable formal language and deciding what to
do by drawing logical consequences.  Representing sentences by list
structure seemed appropriate - it still is - and a list processing
language also seemed appropriate for programming the operations involved
in deduction.

	The first problem was to decide how to do list structure
in the IBM 704.  This computer has a 36 bit word, and two 15 bit
parts, called the address and decrement were distinguished by
special instructions form moving their contents to and from the
15 bit index registers.  The address of the machine was 15 bits,
so it was clear that list structure should use 15 bit pointers.
Therefore, it was natural to consider the word as divided into
4 parts, the address part, the decrement part, the prefix part
and the tag part.  The last two were three bits each and separated
from each other by the decrement so that they could not be easily
combined into a single six bit part.

	At this point there was some indecision about what the basic
operators should be, because the operation of extracting a part of the
word by masking was considered separately from the operation of taking the
contents of a word in memory as a function of its address.  At the time,
it seemed dubious to regard the latter operation as a function, since its
value depended on the contents of memory at the time the operation was
performed, so it didn't act like a proper mathematical function.  However,
the advantages of treating it grammatically as a function so that it could
be composed were also apparent.

	Therefore, the initial set of functions included %2cwr%1,
standing for "Contents of the Word in Register number" and four
functions that extracted the parts of the word and shifted them
to a standard position at the right of the word.  An additional
function of three arguments that would also extract an arbitrary
bit sequence was thrown in just in case it might be useful.

	It was soon noticed that extraction of a subexpression
involved composing the extraction of the address part with %2cwr%1
and that continuing along the list involved composing the extraction
of the decrement part with %2cwr%1.  Therefore, the compounds
%2car%1, standing for "Contents of the Address part of Register
number", and its analogs %2cdr%1, %2cpr%1, and %2ctr%1 were defined.
The motivation for implementing %2car%1 and %2cdr%1 separately was
strengthened by the vulgar fact that the IBM 704 had instructions
(connected with indexing) that made these operations easy to implement.
A construct operation for taking a word off the free storage list
and stuffing it with given contents was also obviously required.
At some point a %2cons(a,d,p,t)%1 was defined, but it was regarded
as a subroutine and not as a function with a value.  This work was
done at Dartmouth, but not on a computer, since the New England
Computation Center was not expected to receive its IBM 704 for
another year.

	In connection with IBM's plane geometry project it was
decided to implement a list
processing language within FORTRAN, because this seemed to the
the easiest way to get started, and, in those days, writing a
compiler for a new language was believed to take many man-years.
This work was undertaken by Herbert Gelernter and Carl Gerberick
at IBM and led to FLPL, standing for FORTRAN List Processing
Language.  Gelernter and Gerberick noticed that
%2cons%1 should be a function, not just a subroutine, and that
its value should be the location of the word that had been
stuffed.  This permitted new expressions to be constructed out
of subsubexpressions by composing occurrences of %2cons%1.

	While expressions could be handled easily in FLPL, and it was
used successfully for the Geometry program, it had neither conditional
expressions nor recursion, and erasing list structure was handled
explicitly by the program.

	Conditional expressions were invented in connection with a set of
chess legal move routines being written in FORTRAN for the IBM 704 at
M.I.T. during 1957-58.  This program did not use list-processing.  The IF
statement provided in FORTRAN 1 and FORTRAN 2 was very awkward to use, and
it was natural to invent a function XIF(M,N1,N2) whose value was N1 or N2
according to whether the expression M was zero or not.  The function
shortened many programs and made them easier to understand, but it had to
be used sparingly, because all three arguments had to be evaluated before
XIF was entered, since XIF was called as an ordinary FORTRAN function
though written in machine language.  This led to the invention of the true
conditional expression which evaluates only one of N1 and N2 according to
whether M is true or false and to a desire for a programming language that
would allow its use.

	A paper defining conditional expressions and proposing their
use in Algol was sent to the %2Communications of the ACM%1 but was
arbitrarily demoted to a letter to the editor, because it was very
short.

	I spent the summer of 1958 at IBM and was attracted to
the problem of differentiating algebraic expressions as an example
of symbolic computation.  The single example of differentiation
led to the following innovations:

	a. Writing recursive function definitions using conditional
expressions.  The idea of differentiation is obviously recursive, and
conditional expressions allowed combining the cases into a single
formula.

	b. The %2maplist%1 function that forms a list of applications of a
functional argument to the elements of a list.  This was obviously wanted
for differentiating sums of arbitrarily many terms.  With a slight
modification to its present form that takes tails of the list as arguments
of the function, it could be applied to differentiating products.

	c. If one is to use functions as arguments, then one needs
a notation for functions, and it seemed natural to use the λ-notation
of Church.  I didn't understand the rest of his book %2Calculi of
Lambda Conversion%1, so I wasn't tempted to try to implement his
more general mechanism for defining functions.  It used higher order
functionals instead of using conditional expressions.  Conditional
expressions are much more readily implemented on computers.

	d. The recursive definition of differentiation made no
provision for erasure of abandoned list structure.  No solution was
apparent at the time, but the idea of complicating the elegant
definition of differentiation by putting in explicit erasure
was unattractive.

	The differentiation program was not actually implemented that
summer, because FLPL allowed neither conditional expressions nor
recursive use of subroutines.


2. The implementation of LISP.

	In the Fall of 1958, I became Assistant Professor of Communication
Sciences (in the EE Department) at M.I.T., and Marvin Minsky (then
an assistant professor in the Mathemtics Department) and I
started the M.I.T. Artificial Intelligence Project.  The Project
was supported by the M.I.T. Research Laboratory of Electronics
which had a contract from the armed services that permitted great
freedom to the Director, Professor Jerome Wiesner, in initiating
new projects that seemed to him of scientific interest.  No written
proposal was ever made.  When Wiesner asked Minsky and me what we
needed for the project, we asked for a room, two programmers,
a secretary and a keypunch,
and we were asked whether we would also undertake the supervision of
some of the six mathematics graduate students that
R.L.E. had undertaken to support.

	The implementation of LISP began in Fall 1958.  The
original idea was to produce a compiler, but this was considered a
major undertaking,
and we needed some experimenting in order to get good conventions
for subroutine linking, stack handling and erasure.  Therefore,
we started by hand-compiling various functions
into assembly language and writing subroutines to provide a LISP
"environment".  These included programs to read and print list structure.
I can't now remember whether the decision to use parenthesized list notation
as the external form of LISP data
was made then or whether it had already been used in discussing the
paper differentiation program.  The erasure problem also had to be
considered, and it was clearly unaesthetic to use explicit erasure
as did IPL.  There were two alternatives.

	The first alternative was to erase the old contents of a
program variable whenever it was updated.  Since the %2car%1 and %2cdr%1
operations were not to copy structure, merging list structure
would occur, and so that erasure would have required a system of
reference counts.  Since there were only six bits left in a word,
and these were in separated parts of the word, reference counts seemed
infeasible without a drastic change in the way list structures were
represented.

	The second alternative is %2garbage collection%1 in which
storage is abandoned until the free storage list is exhausted, the
storage accessible from program variables and the stack is marked,
and the unmarked storage is made into a new free storage list.
Once we decided on garbage collection, its actual implementation
could be postponed, because only toy examples were being done.
(A list handling scheme using reference counts was later used by Collins
on a 48 bit CDC computer).

	At that time it was also decided to use SAVE and UNSAVE
routines that use a single public stack in order save the values of variables
and subroutine return addresses in the implementation of recursive
subroutines.  IPL built stacks as list structure and their use
had to be explicitly programmed.
Another decision was to give up the prefix and tag parts of the
word, to abandon %2cwr%1, and to make %2cons%1 a function of
two arguments.  This left us with only a single type - the
15 bit address - so that
the language didn't require types.

	These simplifications made LISP into a way of describing computable
functions much neater than the Turing machines or general recursive
definitions used in recursive function theory.  The fact
that Turing machines constitute an awkward programming language
doesn't much bother recursive function theorists, because they
almost never have any reason to write particular recursive definitions,
since the theory concerns recursive functions in general.  They often
have reason to prove that recursive functions with specific properties
exist, but this can be done by an informal argument without having
to write them down explicitly.  In the early days of computing, some
people developed programming languages based on Turing machines;
perhaps it seemed more scientific.  Anyway, I decided to write a paper
describing LISP both as a programming language and as a formalism
for doing recursive function theory.  The paper was %2Recursive
functions of symbolic expressions and their computation by machine, part I%1
which appeared in the
%2Communications of the ACM%1 in April 1960.  Part II was never written
but was intended to contain applications to computing with algebraic
expressions.
The paper had no influence on recursive function theorists, because it
didn't address the questions that interested them.

	One way to show that LISP was neater than Turing machines was
to write a universal LISP function and show how much briefer and
more comprehensible it was than the description of a universal
Turing machine.  This was the LISP function %2eval[e,a]%1 that
computes the value of a LISP expression %2e%1 - the second argument
%2a%1 being a list of assignments of values to variables needed to
make the recursion work.  Writing %2eval%1 required inventing a notation
representing LISP functions as LISP data, and such a notation was
devised without much thought for the purposes of the paper.  Logical
completeness required that the notation used to express functions
used as functional arguments be extended to provide for
recursive functions, and the LABEL notation was invented for
that purpose.  D.M.R. Park pointed out that LABEL was logically
unnecessary since the result could be achieved using only LAMBDA -
albeit in a more complicated way.  S.R. Russell,
a programmer for the project, noticed that %2eval%1 could serve
as an interpreter for LISP, promptly hand coded it, and we now had
a programming language with an interpreter.

	The unexpected appearance of an interpreter tended to freeze
the form of the language, and some of the decisions made rather
lightheartedly for the "Recursive functions ..." paper later proved
unfortunate.  These included the COND notation for conditional
expressions which leads to an unnecessary depth of parentheses, and
the use of the number zero to denote the empty list NIL and the
truth value %3false%1.  Besides encouraging pornographic programming,
giving a special interpretation to the address 0 has caused difficulties
in all subsequent implementations.


3. Improvements.  LISP I and LISP 1.5.

	a. Property lists.  The idea of providing each atom with a list
of properties was present in the first assembly language implementation.
It was also one of the theoretical ideas of the Advice Taker, although
the Advice Taker (McCarthy 1959)
would have required a property list for any expression for
about which information was known that did not follow from its structure.
The READ and PRINT programs required that the print names of atoms be
accessible, and as soon as function definition became possible, it was
necessary to indicate whether a function was a SUBR in machine code
or was an EXPR represented by list structure.  Several functions dealing
with property lists were also made available for application
programs which made heavy use of them.

	b. Insertion of elements in lists and their deletion.
One of the original advertised virtues of list processing for AI
work was the ability to insert and delete elements of lists.
Unfortunately, this facility coexists uneasily with shared list
structure.  Moreover, operations that insert and delete don't have
a neat representation as functions.  LISP contains them in the form
of the %2rplaca%1 and %2rplacd%1 pseudo-functions, but programs that
use them cannot be conveniently represented in logic, because, regarded
as functions, they don't permit replacement of equals by equals.

	c. Numbers.  Many computations require both numbers and
symbolic expressions.  Numbers were implemented in LISP I as lists
of atoms, and this was useless for all but the simplest computations.
A reasonably efficient implementation of numbers as atoms in
S-expressions was made in LISP 1.5, but in all the early LISPs,
numerical computations were still 10 to 100 times slower than in
FORTRAN.  Efficient numerical computation requires some form of
typing in the source language and a distinction between numbers
treated by themselves and as elements of S-expressions.

	d. Free variables.  In all innocence, James R. Slagle
programmed the following LISP function definition and complained
when it didn't work right:

	%2testr[x,p,f,u] ← qif p[x] qthen f[x] qelse qif qa x qthen u[]
qelse testr[qd u,p,f,λ:testr[qd u,p,f,u]]%1.

The object of the function is to find a subexpression of ⊗x satisfying
%2p[x]%1 and return ⊗f[x].  If the search is unsuccessful, then the
continuation function ⊗u[] of no arguments is to be computed and its
value returned.  The difficulty was that when an inner recursion
occurred, the value of ⊗u wanted was the outer value, but the inner
value was actually used.  In modern terminology, lexical scoping was
wanted, and dynamic scoping was obtained.

	I must confess that I regarded this difficulty as just a bug
and expressed confidence that Steve Russell would soon fix it.  He did
fix it but by inventing the so-called FUNARG device that took the
lexical environment along with the functional argument.  Similar
difficulties later showed up in Algol 60, and Russell's turned out
to be one of the more comprehensive solutions to the problem.

	e. The "program feature".  Besides composition of functions and
conditional expressions, LISP also allows sequential programs
written with assignment statements and %3go_to%1s.  Compared to
the mathematically elegant recursive function definition features,
the "program feature" looks like a hasty afterthought.  This is not
quite correct; the idea of sequential program antedates that of
recursive function definition.  However, the notation LISP uses
for PROGs was definitely an afterthought and is far from optimal.

	f. Once the %2eval%1 interpreter was programmed, it became
available to the programmer, and it was especially easy to use
because it uses LISP program expressed as LISP data.  In particular,
%2eval%1 made possible FEXPRS and FSUBRS which are "functions"
that are not given their actual arguments but are given the expressions
that evaluate to the arguments and must call %2eval%1 themselves when
they want the expressions evaluated.  The main application of this
facility is to functions that don't always evaluate all of their
arguments; they evaluate some of them first, and then decide which
others to evaluate.  This facility resembles Algol's %2call-by-name%1
but is more flexible, because %2eval%1 is explicitly available.

	g. Since LISP works with lists, it was also convenient to
provide for functions with variable numbers of arguments by supplying
them with a list of arguments rather than the separate arguments.

	Unfortunately, none of the above features has been given
a comprehensive and clear mathematical semantics in connection with
LISP or any other programming language.  The best attempt in connection
with LISP is Michael Gordon's (1973), but it is too complicated.

	As a programming language LISP has many limitations.  Some of
the most evident in the early 1960s were weak numerical computation,
inability to represent objects by blocks of registers and garbage
collect the blocks, and lack of a good system for input-output of
symbolic expressions in conventional notations.  All these problems
and others were to be fixed in LISP 2.  Unfortunately, the LISP 2
project, undertaken by Information International and System
Development Corporation proved too ambitious for the computer that
had to be used and for the budget of the project.  Therefore, we had
to settle for LISP 1.5 developed at M.I.T. which corrected only the
most glaring deficiencies.

	The existence of an interpreter and the absence of declarations
makes it particularly natural to use LISP in a time-sharing environment.
It is convenient to define functions, test them, and re-edit them
without ever leaving the LISP interpreter.  A demonstration of LISP
in a prototype time-sharing environment on the IBM 704 was made in
xxx 1960 (or 1961?).  L. Peter Deutsch implemented the first interactive
LISP on the PDP-1 computer in 1963, but the PDP-1 was had too small
a memory for serious symbolic computation.

	The most important implementations of LISP proved to be
those for the PDP-6 computer and its successor the PDP-10 made
by the Digital Equipment Corporation of Maynard, Massachusetts.
In fact, the half word instructions and the stack instructions
of these machines were developed with LISP's requirements in mind.
The early development of LISP at M.I.T. for this line of machines
and its subsequent development of BBN LISP (aka INTERLISP) and
MACLISP also contributed to making these machines the machines of
choice for artificial intelligence research.  The IBM 704 LISP was
extended to the IBM 7090 and later led to LISPs for the IBM 360
and 370.

	The earliest publications on LISP were in the Quarterly Progress
Reports of the M.I.T. Research Laboratory of Electronics.  (McCarthy 1960)
was the first journal publication.  The %2LISP Programmer's Manual%1 by
Phyllis Fox was published by the Research Laboratory in 196x and the
%2LISP 1.5 Programmer's Manual%1 by McCarthy, Levin, et. al.  in 196x was
published by M.I.T. Press.  After the publication of (McCarthy and Levin
196x), many LISP implementations were made for numerous computers.
However, in contrast the situation with most widely used programming
languages, no organization has ever attempted to propagate LISP, and there
has never been an attempt at agreeing on a standardization, although
recently A.C. Hearn has developed a "standard LISP" that runs on a number
of computers.


4. Conclusions.

	LISP is now the second oldest programming language (after FORTRAN)
in present widespread use.  It owes its longevity to the fact that its
core occupies some kind of local optimum in the space of programming
languages given that static friction discourages purely notational
changes.  Recursive use of conditional expressions, representation of
symbolic information externally by lists and internally by list structure,
and representation of program in the same way will probably have a very
long life.  LISP itself will probably become obsolete when someone
succeeds in making a more comprehensive language that dominates LISP
practically and also gives a clear mathematical semantics to a more
comprehensive set of features.


5. References.


.SKIP TO COLUMN 1
.at "z1" ⊂"%41%*"⊃
.at "zn" ⊂"%4n%*"⊃
APPENDIX I - A MICRO-MANUAL FOR LISP - NOT THE WHOLE TRUTH


	LISP data are symbolic expressions that can be either %2atoms%1 or
%2lists%1.  %2Atoms%1 are strings of letters and digits and other
characters not otherwise used in LISP.  A list consists of a left
parenthesis followed by zero or more atoms or lists separated by spaces
and ending with a right parenthesis.  Examples: A, ONION, (), (A), (A
ONION A), (PLUS 3 (TIMES X PI) 1), (CAR (QUOTE (A B))).

	The LISP programming language is defined by rules whereby certain
LISP expressions have other LISP expressions as %2values%1.
The function called ⊗value that we use in giving these rules
is not part of the LISP language but rather part of the informal
mathematical language used to define LISP.
Likewise, the
italic letters ⊗e and ⊗a (sometimes with subscripts) denote LISP
expressions, the letter ⊗v (usually subscripted) denotes an atom serving
as a variable, and the letter ⊗f stands for a LISP expression serving as a
function name.
.item←0

#. %2value%1 (QUOTE ⊗e) = e.  Thus the value of (QUOTE A) is A.

#. ⊗value (CAR ⊗e), where %2value e%1 is a non-empty list, is the first element
of ⊗value_e.  Thus %2value%1_(CAR (QUOTE (A B C))) = A.

#. ⊗value (CDR e), where ⊗value ⊗e is a non-empty list, is the
the list that remains when the first element
of ⊗value_e is deleted.  Thus %2value%1_(CDR (QUOTE (A B C))) = (B C).

#. ⊗value (CONS ⊗e1 ⊗e2), is the list that results from prefixing
⊗value_e1 onto the list ⊗value_e2.  Thus
%2value%1_(CONS_(QUOTE_A)_(QUOTE_(B_C)))_=_(A_B_C).

#. ⊗value (EQUAL ⊗e1 ⊗e2) is T if ⊗value ⊗e1 = ⊗value ⊗e2.  Otherwise,
its value is NIL.  Thus %2value%1_(EQUAL_(CAR_(QUOTE_(A_B)))_(QUOTE_A))_=_T.

#. ⊗value (ATOM ⊗e) = T if ⊗value ⊗e is an atom; otherwise its
value is NIL.

#. ⊗value (COND(%2pz1 ez1) ... (pzn ezn)) = value e%4i%1,
where %2p%4i%1 is the the first of the %2p%1's whose value is not NIL.
Thus

⊗value (COND ((ATOM (QUOTE A)) (QUOTE B)) ((QUOTE T) (QUOTE C))) = B.

#. An atom ⊗v, regarded as a variable, may have a value.

#. ⊗value ((LAMBDA (%2vz1 ... vzn) e) ez1 ... ezn)%1 is
the same as ⊗value_e but in an environment in which
the variables %2vz1_..._vzn%1 take the values of the
expressions %2ez1_..._ezn%1 in the original environment.  Thus

⊗value ((LAMBDA (X Y) (CONS (CAR X) Y)) (QUOTE (A B)) (CDR (QUOTE (C D))))
= (A D).

#. Here's the hard one.  ⊗value ((LABEL ⊗f (LAMBDA %2(vz1 ... vzn) e))
ez1 ... ezn)%1 is the same as ⊗value ((LAMBDA (%2vz1 ... vzn) e)
ez1 ... ezn)%1 with the additional rule
that whenever %2(f_az1_..._azn)%1 must be evaluated, ⊗f 
is replaced by (LABEL_%2f%1_(LAMBDA_(%2vz1_..._vzn) e))%1.
Lists beginning with LABEL define functions recursively.

	This is the core of LISP, and here are more examples:

⊗value (CAR X) = (A B) if ⊗value X = ((A B) C), and
⊗value ((LABEL FF (LAMBDA (X) (COND ((ATOM X) X) ((QUOTE T) (FF (CAR X))))))
(QUOTE ((A B) C))) = A.
Thus ((LABEL FF (LAMBDA (X) (COND ((ATOM X) X) ((QUOTE T) (FF (CAR X)))))),
is the LISP name of a function ⊗ff such that ⊗ff_e is the
first atom in the written form of ⊗e. 
Note that the list ⊗ff is substituted for the atom FF twice.

Difficult mathematical type exercise: Find a list e such that ⊗value_e_=_e. 

%3Abbreviations%1

	The above LISP needs some abbreviations for practical use.
.item←0
#. The variables T and NIL are permanently assigned the values
T and NIL, and NIL is the name of the null list ().


#. So as not to describe a LISP function 
each time it is used, we define it permanently by typing
(DEFUN %2f (vz1 ... vzn) e)%1.  Thereafter
%2(f ez1 ... ezn)%1 is evaluated by evaluating ⊗e with the variables
%2vz1,_..._,vzn%1 taking the values %2value_ez1,_..._,value_ezn%1
respectively.  Thus, after we define
(DEFUN FF (X) (COND ((ATOM X) X) (T (FF (CAR X))))),
typing  (FF (QUOTE ((A B) C))), gets A from LISP.

#. We have the permanent function definitions

(DEFUN NULL (X) (EQUAL X NIL)) and

(DEFUN CADR (X) (CAR (CDR X))),

and similarly for arbitrary combinations of A and D.

#. (LIST %2ez1 ... ezn%1) is defined for each ⊗n to be
(CONS %2e%1z1 (CONS ... (CONS %2e%1zn NIL))).

#. (AND ⊗p ⊗q) abbreviates
(COND (⊗p ⊗q) (T NIL)).  ANDs with more terms are defined
similarly, and the propositional connectives
OR and NOT are used in abbreviating corresponding conditional expressions.

	Here are more examples of LISP function definitions:

(DEFUN ALT (X) (COND ((OR (NULL X) (NULL (CDR X))) X) (T (CONS (CAR X)
(ALT (CDDR X))))))

defines a function that gives alternate elements of a list starting with
the first element.  Thus
(ALT (QUOTE (A B C D E))) = (A C E).

(DEFUN SUBST (X Y Z) (COND ((ATOM Z) (COND ((EQUAL Z Y) X) (T Z)))
(T (CONS (SUBST X Y (CAR Z)) (SUBST X Y (CDR Z)))))),

where Y is an atom, gives the result of substituting X for Y in Z.  Thus

(SUBST (QUOTE (PLUS X Y)) (QUOTE V) (QUOTE (TIMES X V))) =
(TIMES X (PLUS X Y)).

	You may now program in LISP.  Call LISP on a
time-sharing computer, define some functions, type in a LISP expression,
and LISP will output its value on your terminal.

.skip 1
.begin verbatim
John McCarthy
Artificial Intelligence Laboratory
Computer Science Department
Stanford University
Stanford, California 94305

ARPANET: MCCARTHY@SU-AI
.end

.turn on "{"
%7This draft of
LISP[F77,JMC]
PUBbed at {time} on {date}.%1
Comments by Carl Hewitt on an earlier version and their fate in this version.
.skip to column 1

***In general I think that the paper is a good start.  However, the introductory
paragraph might better serve as a conclusion after to you have introduced and
explained the concepts involved***
[I compromised - making it the second paragraph].

***The following paragraph might be a good place to start the paper***
[This suggestion adopted].

***Perhaps "subexpressions" is better than "subsubexpressions"***fixed
[This suggestion adopted].

***You might want to mention the Advice Taker Project at some point
and explain the relationship of the development of LISP to furthering the
goals of that project***
[done]

***In an appendix it might be worthwhile to present the definition
of EVAL together with the modification that makes upward funargs work.***
Carl: Can you supply me with such an eval?
[I will include the micro-manual as an appendix].

***The following comment about the denotational semantics of RPLACA
and RPLACD seems out of place in the early history of LISP***
[dropped from this place but partially restored further on].

Semantically, they must be represented by functions of state, and only
Michael Gordon really understands them.  All this could not be formulated
precisely while LISP was being developed, but it was clear that
%2rplaca%1 and %2rplacd%1 were anomalous.

***Where did FEXPRS come from?***
[answered].

***How did PROG get introduced into LISP?
Was its introduction merely a concession to the FORTRAN mentality.
At this time you already knew how to translate programs that use
gotos into recursive function calls.  The resulting functions are tail
recursive so they do not need to use up any storage on the pushdown stack
either interpreted or compiled (see my recent paper in the
A.I. Journal on "Viewing Control Structures as Patterns of Passing
Messages")***
[answered].

***You might also want to mention the pdp-1 LISP system developed by
Peter Deutsch.  Was the PDP-1 system the first LISP system to be used
interactively?***
[Don't know.].

***Contemporaneous with the development of the LISP 2 project was the
development of MACLISP on the PDP-6.   In fact Alan Kotok explicitly
put the half word instructions into the PDP-6 order code partly as a result
of seeing how useful they would be in the implementation of LISP****
[PDP-6 and its role in LISP discussed].

***Why was the function LABEL was included in LISP?***
[answered].

***Why were RPLACA and RPLACD considered to be more anomalous than
PUTPROP and GETPROP?***
[I don't want to discuss the property list functions].

***The following paragraph makes a good point that could be backed up with
specific examples if the paragraph were placed later in the paper***
[This point not specifically responded to].

***The next paragraph seems a bit disjointed.  Many topics have
been superficially mentioned so far.  Perhaps a better approach
is to cover the topics in historical order as you do later in the paper***
[I made it the second paragraph].

	In addition to its core consisting of recursive conditional
expression and Boolean expression definitions built up from the
three functions %2car%1, %2cdr%1 and %2cons%1 and the predicates
%2atom%1 and %2eq%1, LISP has many features adopted from other
programming languages of the late fifties and early sixties.
A recurrent issue has always been how to handle free variables in function
definitions.  This problem has also plagued Algol and other programming
languages, and a compromise has always been necessary between definitional
power and high speed implementation by interpreters and compilers.
[omitted as suggested].

***The compatibility between the LISP compiler and interpreter
has been one of its most important innnovations.  This allows
the convenience of interactive editing and debugging afforded by
interpreters while preserving the efficiency that can be obtained
from compiled code.  However, the LISP interpreter and compiler
were nor perfectly compatible.  You might usefully discuss
SPECIAL and COMMON variables.***
[Tentatively, I have decided not to raise this issue; you might
raise it in commentary if you want].